package top.hkyzf.study.leetcode.linkedlist;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * description: 
 * @author zhufeng
 * @date 2023/4/10 17:17
 * @version V1.0
 */
public class 链表中的下一个更大节点_1019 {

    @Test
    public void testNextLargerNodes () {
        ListNode node4 = new ListNode(5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(4, node3);
        ListNode node1 = new ListNode(7, node2);
        ListNode head = new ListNode(2, node1);
        int[] ints = nextLargerNodes(head);
        for (int i : ints) {
            System.out.println(i);
        }
    }

    public int[] nextLargerNodes(ListNode head) {
        Deque<int[]> stack = new ArrayDeque<>();
        List<Integer> result = new ArrayList<>();
        if (head == null) {
            return null;
        }
        int index = -1;
        while (head != null) {
            index++;
            while (!stack.isEmpty() && stack.peek()[1] < head.val) {
                int[] max = stack.pop();
                result.set(max[0], head.val);
            }
            stack.push(new int[]{index, head.val});
            result.add(0);
            head = head.next;
        }
        int size = result.size();
        int[] rtn = new int[size];
        for (int i = 0; i < size; i++) {
            rtn[i] = result.get(i);
        }
        return rtn;
    }
}
